<TITLE>prob003: quasigroup existence</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob003: quasigroup existence</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.york.ac.uk/~tw">
          <B>Toby Walsh</B></A> 
          <ADDRESS><a href="mailto:tw@cs.york.ac.uk">
          tw@cs.york.ac.uk</a></ADDRESS>
</TABLE>
with assistance from Kostas Stergiou and Mark Stickel. 
</CENTER>
<HR><!------------------------------------------------------------------------>
<H3> Models </H3>
Quasigroup existence problems have been modelled using
either m^2 variables each of domain size m (with v_ij=k iff 
i*j=k) or
m^3 0-1 variables (with v_ijk=True iff 
i*j=k). I am unaware of any direct
comparisons between these two approaches. 
<P>
Symmetry breaking is crucial to the efficient
solution of these problems. One symmetry breaking
constraint often added is that
that a*m >= a-1 where m is the order of
the quasigroup. 
<P>
In the model with m^2 variables,
the constraint that each element occurs once in every
row and column gives 2m all-different constraints,
each between m variables. Using a specialized
constraint propagation algorithm for this 
type of constraint can reduce search greatly.

<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


